#pragma once

#include <assert.h>
#include <xstring>
#include <tchar.h>

#ifndef __LIST_H__
#define __LIST_H__

#ifdef _DEBUG
	#define LIST_ASSERT
#endif



class list_exc 
{
public:
	enum errCode {NOINIT = 2,ENDLIST = 4,NOTCURRENT=8,NOTPARENT=16};
	list_exc (const errCode &err_code = NOINIT, const std::wstring &m = _T("") ):error_code(err_code),msg(m){};
	~list_exc (){};
std::wstring msg;
list_exc::errCode error_code;

};


template <class T>
class DLinkedList
{
public:
	class DListNode
	{
	public:
		T data;
		DListNode* next;
		DListNode* previous;
	};
	//-------------------
	class iterator
	{
	
	public:
		DListNode* node;
		DLinkedList* list;

		iterator(){
			list = NULL; node = NULL; 	
		};

		iterator (DLinkedList*l, DListNode* n){		
			list = l; node = n; 	
		};
		
		~iterator(){
		};
	
		iterator (iterator *l)		{	list = l->list; Start ();		};

	public:
		
		void forward()
		{
			#ifdef LIST_ASSERT
				assert (list != NULL);
				assert (node != NULL);
			#else
				if (!list) throw list_exc(list_exc::NOINIT);
				if (!node) throw list_exc(list_exc::NOINIT);
			#endif
			
			node = node->next;
		};
		void backward()
		{
			#ifdef LIST_ASSERT
				assert (list != NULL);
				assert (node != NULL);
			#else
				if (!list) throw list_exc(list_exc::NOINIT);
				if (!node) throw list_exc(list_exc::NOINIT);
			#endif
			
			node = node->previous;
		};
		bool valid()
		{
			#ifdef LIST_ASSERT
				assert (list != NULL);
				assert (node != NULL);
			#else
				if (!list) throw list_exc(list_exc::NOINIT);
				if (!node) throw list_exc(list_exc::NOINIT);
			#endif

			return true;
		};

		DListNode* start ()
		{
			#ifdef LIST_ASSERT
				assert (list != NULL);
				assert (node != NULL);
			#else
				if (!list) throw list_exc(list_exc::NOINIT);
				if (!node) throw list_exc(list_exc::NOINIT);
			#endif

			node = list->head;//node->previous;
			return node;
		};

		DListNode* end ()
		{
			#ifdef LIST_ASSERT
				assert (list != NULL);
				assert (node != NULL);
			#else
				if (!list) throw list_exc(list_exc::NOINIT);
				if (!node) throw list_exc(list_exc::NOINIT);
			#endif

			node = list->tail;//node->previous;
			return node;

		};

		bool last ()
		{
			#ifdef LIST_ASSERT
				assert (list != NULL);
				assert (node != NULL);
			#else
				if (!list) throw list_exc(list_exc::NOINIT);
				if (!node) throw list_exc(list_exc::NOINIT);
			#endif

			if (node == list->tail) 
				return true;
			
			return false;
		}

		iterator& operator += (int i) 
		{
			#ifdef LIST_ASSERT
				assert (list != NULL);
				assert (node != NULL);
			#else
				if (!list) throw list_exc(list_exc::NOINIT);
				if (!node) throw list_exc(list_exc::NOINIT);
			#endif

			for (int i_ = 0; i_ < i ; i_++)
			{
				if (node != list->tail)
					forward();
				else
					*this = list->end();
			}
			
			return (*this); 
		}

		iterator& operator ++ () 
		{
			#ifdef LIST_ASSERT
				assert (list != NULL);
				assert (node != NULL);
			#else
				if (!list) throw list_exc(list_exc::NOINIT);
				if (!node) throw list_exc(list_exc::NOINIT);
			#endif

			if (node != list->tail)
				forward();
			else
				*this = list->end();
			

			return (*this); 
		}
		iterator& operator ++ (int) 
		{
			++(*this);
			return (*this);
		}
		operator bool ()			{ return ( (node != NULL)&&(list!=NULL) );		}

		const iterator& operator = (const iterator& iter)
		{


			node = iter.node;
			list = iter.list;

			return (*this);
		}

		// copy CTOR	- do via operator =
		iterator (const iterator& iter):node (iter.node), list(iter.list)	{
			//(*this) = iter ;
		}	

		bool operator == (const iterator& iter) const
		{
		
			if (node == iter.node  &&  list == iter.list )
				return (true);
			else
				return (false);
			return false;
		}


		bool operator != (const iterator& iter) const		{
			return (! operator == (iter) ); 	
		}

		T* operator -> ()		{	return (*this);	}
		T& operator * ()		{	
			#ifdef LIST_ASSERT
				assert (list != NULL);
				assert (node != NULL);
			#else
				if (!list) throw list_exc(list_exc::NOINIT);
				if (!node) throw list_exc(list_exc::NOINIT);
			#endif
			
			return (node->data);
			
		}
	};
public:
	DListNode* head;
	DListNode* tail;
private:
	iterator it_tmp;
	unsigned long count;
public:
	DLinkedList () : head(NULL), tail(NULL), count(0)	{};
	~DLinkedList(){
		DListNode* temp;
		while (head != NULL)
		{
			temp = head->next;
			delete head;
			head = temp;
		}
	};
	inline iterator &push_back(T d)
	{
		DListNode* temp = new DListNode ();
		if (count > 0)
		{
			
			temp->next = NULL;
			temp->previous = tail;
			temp->data = d;
			tail->next = temp;
			tail = temp;
			count++;
		}
		else if (count == 0)
		{
			temp->next = NULL;
			temp->previous = NULL;
			temp->data = d;
			head = tail = temp;
			count++;
		}

		it_tmp = iterator (this, temp);
		return it_tmp;

	};
	void push_front(T d)
	{
		if (count > 0)
		{
			DListNode* temp = new DListNode<T>;
			temp->next = head;
			temp->previous = NULL;
			temp->data = d;
			head->previous = temp;
			head = temp;
			count++;
		}
		else if (count == 0)
		{
			DListNode* temp = new DListNode<T>;
			temp->next = NULL;
			temp->previous = NULL;
			temp->data = d;
			head = tail = temp;
			count++;
		}
	};
	void pop_front()
	{
		if (count == 1)
		{
			delete head;
			head = tail = NULL;
			count--;
		}
		else if (count == 2)
		{
			delete head;
			tail->previous = NULL;
			head = tail;
			count--;
		}
		else if (count > 2)
		{
			DListNode<T>* temp = head->next;
			delete head;
			head = temp;
			head->previous = NULL;
			count--;
		}
	};
	void pop_back()
	{
	if (count == 1)
	{
		delete tail;
		head = tail = NULL;
		count--;
	}
	else if (count == 2)
	{
		delete tail;
		head->next = NULL;
		tail = head;
		count--;
	}
	else if (count > 2)
	{
		DListNode<T>* temp = tail->previous;
		delete tail;
		tail = temp;
		tail->next = NULL;
		count--;
	}
};
	void remove  (iterator& itr)
	{
		if (count == 1)
		{
			delete head;
			head = tail = itr.node = NULL;
			count--;
		}
		if (count > 1 && itr.Valid())
		{
			if (itr.node == tail)
			{
				tail = itr.node->previous;
				delete itr.node;
				tail->next = NULL;
				itr.node = head;
			}
			if (itr.node == head)
			{
				head = itr.node->next;
				delete itr.node;
				head->previous = NULL;
				itr.node = head;
			}
			else
			{
				DListNode<T>* next = itr.node->next;
				DListNode<T>* prev = itr.node->previous;
				next->previous = prev;
				prev->next = next;
				delete itr.node;
				itr.node = next;			
			}
			count--;
		}
	};
	
	iterator &insert_after  (iterator& itr, T d)
	{
		DListNode* temp = new DListNode();
		if (count == 0)
		{
			
			head = tail = temp;
			head->next = NULL;
			head->previous = NULL;
			head->data = d;
			itr.node = head;
			count++;
		}
		else if (count == 1 && itr.valid())
		{
			
			temp->previous = head;
			temp->next = NULL;
			temp->data = d;

			head->next = temp;
			
			tail =  temp;
			count++;
		}
		else if (count > 1 && itr.valid())
		{
			if (itr.node == tail)
			{
				
				temp->previous = itr.node;
				temp->data = d;
				temp->next = NULL;
				
				tail->next = temp;
				tail =  temp;
			}
			else
			{
			
				temp->previous = itr.node;
				temp->next = itr.node->next;
				temp->data = d;

				itr.node->next = temp;
	
			}
			count++;
		}

		it_tmp = iterator (this, temp);
		return it_tmp;
		

	};
	iterator &insert_before  (iterator& itr, T d)
	{
		DListNode* temp = new DListNode();
		temp->data = d;
		
		if (count == 0)
		{
			head = tail = temp;
			head->previous = NULL;
			head->next = NULL;
			itr.node = head;
			//count++;
		}
		else if (count == 1 && itr.valid())
		{
			
			temp->previous = NULL;//head;
			temp->next = head/*NULL*/;

			head->next = NULL;
			head->previous = temp;
			
			
			tail = head;
			head = temp;
			
			//count++;
		}
		else if (count > 1 && itr.valid())
		{
			if (itr.node == head)
			{

				temp->previous = NULL;
				temp->next = itr.node;

				itr.node->previous = temp;
								
				head = temp;
			}
			else
			{
				itr.node->previous->next = temp;
				temp->previous = itr.node->previous;

				temp->next = itr.node;
				itr.node->previous = temp;
				
			}
			count++;
		}

		it_tmp = iterator (this, temp);
		return it_tmp;

	};

	long size ()const{return count;};

	iterator begin ()		{	return ( iterator ( this, head) );		}
	iterator end ()			{	return ( iterator ( this, NULL) );		}
};
	

#endif